package org.zlb.algorithm.sort;

/**
 * 计数排序，一定范围内排序时复杂度为 o(n+k),范围k越大效率越差
 *
 * @author zhoulingbo
 * @date 2021/7/15 17:10
 */
public class CountingSort extends AbstractSort {

    @Override
    public void sort(int[] arr) {
        int min = arr[0], max = arr[0];
        for (int i=0; i<arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        if (max <= min)
            return;

        int[] temps = new int[max-min+1];
        for (int i=0; i<arr.length; i++) {
            int index = arr[i] - min;
            temps[index] ++;
        }

        int k = 0;
        for (int i=0; i<temps.length; i++) {
            while (temps[i] > 0) {
                arr[k++] = min + i;
                temps[i] --;
            }
        }
    }
}
